package com.wxg.algorithm.chapter04;

import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

public class HeapSortV3<T extends Comparable> implements ISort<T> {
    @Override
    public void sort(T[] arr) {
        int n = arr.length;

        for (int i = (n-1)/2; i>=0; i--){
            shiftDown(arr, n, i);
        }

        for (int i = n-1; i > 0; i--){
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    private void swap(T[] arr, int a, int b) {
        T temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    private void shiftDown(T[] arr, int n, int k) {
        while ( 2*k+1 < n){
            int j = 2*k + 1;
            if ( j + 1 < n && arr[j+1].compareTo(arr[j]) > 0){
                j += 1;
            }

            if ( arr[k].compareTo(arr[j]) >= 0 ){
                break;
            }

            swap(arr, k, j);
            k = j;
        }
    }

    public static void main(String[] args) {
        HeapSortV1<Integer> hs01 = new HeapSortV1<>();
        HeapSortV2<Integer> hs02 = new HeapSortV2<>();
        HeapSortV3<Integer> hs03 = new HeapSortV3<>();

        int n = 1000000;
        Integer[] intArr01 = SortTestHelper.generateRandomArray(n, 0, n);
        Integer[] intArr03 = SortTestHelper.copyIntArray(intArr01);
        Integer[] intArr05 = SortTestHelper.copyIntArray(intArr01);

        SortTestHelper.testSort(hs01, intArr01);
        SortTestHelper.testSort(hs02, intArr03);
        SortTestHelper.testSort(hs03, intArr05);

        Integer[] intArr02 = SortTestHelper.generateNearlyOrderedArray(n, 100);
        Integer[] intArr04 = SortTestHelper.copyIntArray(intArr02);
        Integer[] intArr06 = SortTestHelper.copyIntArray(intArr02);

        SortTestHelper.testSort(hs01, intArr02);
        SortTestHelper.testSort(hs02, intArr04);
        SortTestHelper.testSort(hs03, intArr06);


    }
}
